#include "graph.hpp"
#include <string.h>
void test_matrix()
{

    matrix::Graph<char, int> g("ABCDEFGHI", 9);
    g.addedge('A', 'B', 1);
    g.addedge('A', 'D', 1);
    g.addedge('B', 'E', 1);
    g.addedge('E', 'G', 1);
    g.addedge('C', 'F', 1);
    g.addedge('F', 'H', 1);
    g.addedge('H', 'I', 1);
    g.DFS('A');
}

void test_table()
{
    string a[] = {"张三", "李四", "王五", "赵六"};
    link_table::Graph<string, int> g1(a, 4);
    g1.addedge("张三", "李四", 100);
    g1.addedge("张三", "王五", 200);
    g1.addedge("王五", "赵六", 30);
}

void leaset_tree()
{
    const char *str = "abcdefghi";
    matrix::Graph<char, int> g(str, strlen(str));
    g.addedge('a', 'b', 4);
    g.addedge('a', 'h', 8);
    // g.AddEdge('a', 'h', 9);
    g.addedge('b', 'c', 8);
    g.addedge('b', 'h', 11);
    g.addedge('c', 'i', 2);
    g.addedge('c', 'f', 4);
    g.addedge('c', 'd', 7);
    g.addedge('d', 'f', 14);
    g.addedge('d', 'e', 9);
    g.addedge('e', 'f', 10);
    g.addedge('f', 'g', 2);
    g.addedge('g', 'h', 1);
    g.addedge('g', 'i', 6);
    g.addedge('h', 'i', 7);
    //构建一颗最小生成树
    matrix::Graph<char, int> mintree;
    g.Prim(mintree, 'a');
    mintree.Print();
}
void TestGraphDijkstra()
{
    const char *str = "syztx";
    matrix::Graph<char, int, MAX, true> g(str, strlen(str));
    g.addedge('s', 't', 10);
    g.addedge('s', 'y', 5);
    g.addedge('y', 't', 3);
    g.addedge('y', 'x', 9);
    g.addedge('y', 'z', 2);
    g.addedge('z', 's', 7);
    g.addedge('z', 'x', 6);
    g.addedge('t', 'y', 2);
    g.addedge('t', 'x', 1);
    g.addedge('x', 'z', 4);
    vector<int> dist;
    vector<int> parentPath;
    g.Dijkstra('s', dist, parentPath);
    g.PrintShortPath('s', dist, parentPath);
    for (auto &d : dist)
    {
        cout << d << " ";
    }
    cout << endl;
}

void TestFloydWarShall()
{
    const char *str = "12345";
    matrix::Graph<char, int,MAX,true> g(str, strlen(str));
    g.addedge('1', '2', 3);
    g.addedge('1', '3', 8);
    g.addedge('1', '5', -4);
    g.addedge('2', '4', 1);
    g.addedge('2', '5', 7);
    g.addedge('3', '2', 4);
    g.addedge('4', '1', 2);
    g.addedge('4', '3', -5);
    g.addedge('5', '4', 6);
    vector<vector<int>> vvDist;
    vector<vector<int>> vvParentPath;
    g.FloydWarshall(vvDist, vvParentPath);
    // 打印任意两点之间的最短路径
    for (size_t i = 0; i < strlen(str); ++i)
    {
        g.PrintShortPath(str[i], vvDist[i], vvParentPath[i]);
        cout << endl;
    }
}

int main()
{
    // leaset_tree_Kruskal();
    // leaset_tree_prim();
    //TestGraphDijkstra();
    //leaset_tree();

    TestFloydWarShall();
    return 0;
}